package leetcode;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.stream.Collectors;

public class Lc39 {

    List<List<Integer>> ans;
    HashSet<String> set;
    int start;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ans = new ArrayList<>();
        set = new HashSet<>();
        Arrays.sort(candidates);
        start = 0;
        getAns(candidates, target, new ArrayList<Integer>(), start);
        return ans;
    }

    public void getAns(int[] candidates, int target, List<Integer> list, int start) {
        if (target == 0) {
            String temp = list.stream().sorted().map(String::valueOf).collect(Collectors.joining(","));
            if (set.contains(temp)) return;
            ans.add(new ArrayList<>(list));
            set.add(temp);
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (target < candidates[i]) {
                break;
            }
            list.add(candidates[i]);
            getAns(candidates, target - candidates[i], list, start);
            list.remove(list.size() - 1);
        }
        start++;
    }
}
